#include<bits/stdc++.h>
using namespace std;
namespace IO{
    const int BUF=1<<21;
    char buff[BUF],*p1=buff,*p2=buff;
    #define gc() (p1==p2&&(p2=((p1=buff)+fread(buff,1,BUF,stdin)),p1==p2)?EOF:*p1++)
    template<typename T>inline void read(T &x){
        char ch=gc();x=0;int f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
        x*=f;
    }
    char obuf[BUF],*p3=obuf;
    inline void pc(char ch){
        if(p3-obuf<BUF) *p3++=ch;
        else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;
    }
    inline void put(const char *s){while(*s) pc(*s),++s;}
    char ch[32];int ctop;
    template<typename T>inline void print(T x){
    	if(x<0) x=~x+1,pc('-');
        if(!x) return pc(48);
        while(x) ch[++ctop]=x%10^48,x/=10;
        while(ctop) pc(ch[ctop--]);
    }
    inline void flush(){fwrite(obuf,p3-obuf,1,stdout);p3=obuf;}
}
using namespace IO;
const int N=5e5+5;
int n,m,q,f[N],g[N],a[N],ans[N],vis[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int gind(int x){return g[x]==x?x:g[x]=gind(g[x]);}
vector<pair<int,int>> Q[N];
struct Tree{
	int tagr,tag,tags,ds;
}t[1<<20];
#define mid ((l+r)>>1)
inline void ins1(int p,int v){
	if(t[p].tagr){
		t[p].tags=min(t[p].tags,v-t[p].tagr+1);
	}
	t[p].tag=v;
}
inline void ins2(int p,int v){
	t[p].tag=0;
	t[p].tagr=v;
}
inline void ins3(int p,int v){
	t[p].tags=min(t[p].tags,v);
}
inline void ins4(int p){
	t[p].tags=N,t[p].ds=1;
}
inline void pushdown(int p){
	if(t[p].ds){
		ins4(2*p),ins4(2*p+1);
		t[p].ds=0;
	}
	if(t[p].tagr){
		ins2(2*p,t[p].tagr),ins2(2*p+1,t[p].tagr);
		t[p].tagr=0;
	}
	if(t[p].tag){
		ins1(2*p,t[p].tag),ins1(2*p+1,t[p].tag);
		t[p].tag=0;
	}
	if(t[p].tags<N){
		ins3(2*p,t[p].tags),ins3(2*p+1,t[p].tags);
		t[p].tags=N;
	}
}
void build(int p,int l,int r){
	t[p].tags=N;
	if(l==r) t[p].tagr=l;
	else build(2*p,l,mid),build(2*p+1,mid+1,r);
}
void change1(int p,int l,int r,int lt,int rt,int v){
	if(lt<=l&&r<=rt) return ins1(p,v),ins4(p),void();
	pushdown(p);
	if(lt<=mid) change1(2*p,l,mid,lt,rt,v);
	if(mid<rt) change1(2*p+1,mid+1,r,lt,rt,v);
}
void change2(int p,int l,int r,int lt,int rt,int v1,int v2){
	if(lt<=l&&r<=rt) return ins2(p,v1),ins3(p,v2),void();
	pushdown(p);
	if(lt<=mid) change2(2*p,l,mid,lt,rt,v1,v2);
	if(mid<rt) change2(2*p+1,mid+1,r,lt,rt,v1,v2);
}
int now;
int query(int p,int l,int r,int x){
	if(l==r){
	//	if(now==25) cerr<<"T"<<t[p].tag<<' '<<t[p].tagr<<' '<<t[p].tags<<'\n';
	//	if(!t[p].tag&&t[p].tags>=N) cerr<<"Wdf\n";
		return min(t[p].tag?t[p].tag-t[p].tagr+1:N,t[p].tags);
	}
	pushdown(p);
	return x<=mid?query(2*p,l,mid,x):query(2*p+1,mid+1,r,x);
}
int main(){
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	read(n),read(m),read(q);
	for(int i=1;i<=n;++i) f[i]=i;
	while(m--){
		int x,y;
		read(x),read(y);
		f[find(x)]=find(y);
	}
	for(int i=1;i<=n;++i) a[i]=find(i);
	for(int i=1;i<=q;++i){
		int l,r;
		read(l),read(r);
		Q[r].push_back({l,i});
	
	}
	for(int i=1;i<=n;++i) f[i]=g[i]=i;
	build(1,1,n);
	for(int i=1;i<=n;++i){
		int j=vis[a[i]];
		f[j]=j+1;
		if(j) g[j]=j-1;
		int x=gind(j),y=find(j);
	//	cerr<<i<<' '<<j<<' '<<x<<' '<<y<<'\n';
		change1(1,1,n,j+1,i,i);
	//	if(i>=35&&j<=51) cerr<<"X"<<x<<' '<<j<<'\n';
		if(j) change2(1,1,n,x+1,j,y,i-y+1);
		for(auto v:Q[i]) now=v.second,ans[v.second]=query(1,1,n,v.first);
		vis[a[i]]=i;
		//if(i==35) cerr<<"Qr"<<query(1,1,n,7)<<'\n';
	}
	for(int i=1;i<=q;++i) print(ans[i]),pc('\n');
	flush();
	return 0;
}


